1. Field of the Invention
The present invention relates to a variable length code multiplexer that multiplexes a plurality of input codes including a variable length code into a multiplexed code and a variable length code demultiplexer that demultiplexes the multiplexed code into a plurality of output codes. Particularly, it relates to a variable length code multiplexer suitable for transmitting a multiplexed code by way of a path onto which bit errors can be piggybacked, and a variable length code demultiplexer that pairs up with the variable length code multiplexer.
2. Description of Related Art
A variable length code, such as a Huffman code, is often used to compress various multimedia signals such as a musical sound, a voice, a still picture, and a moving picture, into a small amount of information. Huffman codes are typical variable length codes having a feature that their code length becomes short when they have a frequently used value and becomes long otherwise.
In a sound encoder and a sound decoder disclosed in “ITU-T Recommendation G.722.1” (in September, 1999), a Huffman code is used as a part of codes in order to reproduce an excellent sound signal even when those codes have a small amount of information, and the sound encoder includes a variable length code multiplexer for multiplexing the plurality of codes including the variable length code into a multiplexed code and the sound decoder includes a variable length code demultiplexer for demultiplexing the multiplexed code into the plurality of codes.
FIG. 10 is a block diagram showing the structure of the prior art sound encoder including the variable length code multiplexer, as disclosed in the above-mentioned reference. In the figure, reference numeral 1 denotes an encoding unit for encoding a sound signal 101 so as to produce and output a plurality of input codes 102, and reference numeral 2 denotes a multiplexing unit, which is disposed as the variable length code multiplexer, for multiplexing the plurality of input codes 102 into a multiplexed code 121 so that they are running in a forward direction and for outputting the multiplexed code 121. An envelope code 102-1, a category code 102-2, and a plurality of band-by-band codes 102-3 are included in the plurality of input codes 102 output by the encoding unit 1.
In the multiplexing unit 2 of FIG. 10, reference numeral 22 denotes a forward direction multiplexing unit that stores the plurality of input codes 102, i.e., the envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3 one by one in a memory 24 so that they are running in a forward direction from a head of the memory 24 to a tail of the memory 24 in that order. The multiplexing unit 2 consists of the forward direction multiplexing unit 22 and the memory 24 for temporarily storing the multiplexed code 121.
FIG. 11 is a block diagram showing the structure of the prior art sound decoder including the variable length code demultiplexer, as disclosed in the above-mentioned reference. In the figure, reference numeral 5 denotes a demultiplexing unit, which is disposed as the variable length code demultiplexer, for demultiplexing the multiplexed code 121 from the sound encoder into a plurality of output codes 103 so that they are separated from locations of a memory running in the forward direction and for outputting them, and reference numeral 6 denotes a decoding unit for decoding the plurality of output codes 103 so as to reproduce and output a sound signal 101. The envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3 are included in the plurality of output codes 103 output from the demultiplexing unit 5.
Furthermore, in the demultiplexing unit 5 of FIG. 11, reference numeral 51 denotes a memory for temporarily storing the multiplexed code 121, and reference numeral 52 denotes a forward direction demultiplexing unit for reading the plurality of output codes 103, i.e., the envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3 one by one so that they are separated from locations running in the forward direction from a head of the memory 51 to a tail of the memory 51 in order to demultiplex the multiplexed code 121 stored in the memory 51 into the plurality of output codes 103. The demultiplexing unit 5 consists of the memory 51 and the forward direction demultiplexing unit 52.
Next, a description will be made as to the operation of the prior art sound encoder and the operation of the prior art sound decoder. The prior art sound encoder shown in FIG. 10 performs all processes on a frame-by-frame basis, each frame having a length of 20 ms. When a sound signal 101 is input to the encoding unit 1, the encoding unit 1 performs a modulated lapped transform (MLT) on the sound signal 101 so as to acquire MLT coefficients and divides these MLT coefficients into a plurality of regions. The encoding unit 1 then calculates a mean value of the MLT coefficients for each region and variable length encodes (Huffman encodes) an amplitude envelope which consists of a plurality of acquired mean values so as to output the coded amplitude envelope as the envelope code 102-1.
The encoding unit 1 then normalizes the MLT coefficients for each region with a value obtained by decoding the envelope code 102-1, quantizes the normalized MLT coefficients for each region, and acquires a fixed length code of length which is fixed for each quantization. The encoding unit 1 Huffman-encodes this fixed length code and outputs the acquired variable length code as each band-by-band code 102-3.
The encoding unit 1 determines and outputs the category code 102-2 of a fixed length for controlling the quantization stepsize for each region so that the total code length of the envelope code 102-1 and the band-by-band codes 102-3 is equal to or less than a fixed value. When the total code length is not equal to or less than the fixed value for all candidates for the category codes 102-2, the encoding unit 1 selects a candidate for the category code 102-2 that minimizes the total code length.
The envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3, which are the plurality of input codes 102 output from the encoding unit 1, are input to the multiplexing unit 2, which is disposed as the variable length code multiplexer. The memory 24 in the multiplexing unit 2 is a temporary memory used for forming the multiplexed code 121, and has a storage area of a fixed length which depends on the encoding unit 1. Every time a plurality of input codes 102 are input to the multiplexing unit 2, the memory 24 is so initialized as to have a storage area of a fixed value.
The forward direction multiplexing unit 22 in the multiplexing unit 2 stores the envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3 applied thereto in the memory 24 one by one so that they are running in the forward direction from the head of the memory 24 to the tail of the memory 24. Since the tail of the memory 24 is fixed, the forward direction multiplexing unit 22 does not store any other code after the forward direction multiplexing unit 22 stores the envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3 one by one in the memory 24 and the location in which further data is to be stored in the memory reaches the tail of the memory.
When the forward direction multiplexing unit 22 completes the storing process, the multiplexing unit 2 outputs a value stored in the storage area extending from the head of the memory 24 to the tail of the memory 24 as the multiplexed code 121.
The memory 51 in the demultiplexing unit 5 in FIG. 11 has a storage area of the same length as that of the memory 24 in the multiplexing unit 2 shown in FIG. 10, and stores the multiplexed code 121 output from the multiplexing unit 2 therein.
The forward direction demultiplexing unit 52 in the demultiplexing unit 5 demultiplexes the multiplexed code into the envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3 one by one by reading them bit by bit so that they are separated from locations of the memory 51 running in the forward direction from the head of the memory 51 to the tail of the memory 51, and outputs them to the decoding unit 6 as a plurality of output codes 103.
The decoding unit 6 decodes the envelope code 102-1 so as to calculate an amplitude envelope, calculates a quantization stepsize based on the category code 102-2, decodes each band-by-band code 102-3 based on this quantization stepsize, calculates normalized frequency domain coefficients (e.g., normalized MLT coefficients), denormalizes the frequency domain coefficients by multiplying the value of the amplitude envelope for each region by the normalized frequency domain coefficients for each region, and performs a frequency to time domain transformation, such as an Inverse MLT (IMLT), on the denormalized frequency domain coefficients so as to reproduce a sound signal 101.
FIG. 12 is a diagram showing the structure of the multiplexed code 121 processed by the prior art variable length code multiplexer and the prior art variable length code demultiplexer. As shown in the figure, the envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3 numbered (1) through (14) are multiplexed into a fixed area of the multiplexed code 121. The band-by-band code 102-3 numbered (1) is the one for the region of the lowest frequency. The higher number is assigned to each of the plurality of band-by-band codes 102-3, the higher frequency region each of the plurality of band-by-band codes 102-3 corresponds to. In FIG. 12, “HEAD” indicates the head of the multiplexed code 121, and “TAIL” indicates the tail of the multiplexed code 121.
The forward direction multiplexing unit 22 in FIG. 10 stores the envelope code 102-1 bit by bit in the memory 24 so that it is running in the forward direction toward the tail of the memory 24, by defining the head of the memory 24 as a start location. The forward direction multiplexing unit 22 then defines the next bit position next to the end location in which the envelope code 102-1 is stored, as the next start location in which the category code 102-2 is to be stored, and stores the category code 102-2 bit by bit in the memory 24 so that it is running in the forward direction toward the tail of the memory 24. The forward direction multiplexing unit 22, in turn, stores the plurality of band-by-band codes 102-3 numbered (1) through (14) one by one in the memory 24 so that they are running in the forward direction toward the tail of the memory 24 in the order of the numbers (1) to (14).
The multiplexing unit 2 thus multiplexes all of the envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3 into the multiplexed code 121 as shown in FIG. 12 so that they are running in the forward direction from the head of the multiplexed code 121 to the tail of the multiplexed code 121 in that order.
The forward direction demultiplexing unit 52 as shown in FIG. 11 separates the envelope code 102-1 from the multiplexed code 121, as shown in the FIG. 12, stored in the memory 51 by reading it bit by bit from locations of the memory 51 running in the forward direction toward the tail of the memory 51 by defining the head of the memory 51 as the start location. In the case of demultiplexing of a Huffman code, it is determined that a location where a series of bits read out of the memory matches up with any one of elements included in an encoding table used for the Huffman coding is the boundary between the Huffman code and another code.
The forward direction demultiplexing unit 52 then defines the next bit position next to the end location from which the envelope code 102-1 is to be separated as the start location, and separates the category code 102-2 by reading a fixed number of bits from locations of the memory 51 running in the forward direction toward the tail of the memory 51. The forward direction multiplexing unit 22, in turn, separates the plurality of band-by-band codes 102-3 numbered (1) through (14) one by one from locations of the memory 51 running in the forward direction toward the tail of the memory 51 in the order of the numbers (1) to (14).
The forward demultiplexing unit 52 thus demultiplexes the multiplexed code 121 stored in the memory 51 into the envelope code 102-1, the category code 102-2, and the plurality of band-by-band codes 102-3 by reading them one by one from locations of the memory running in the forward direction from the head of the memory 51 to the tail of the memory 51 in that order.
When a bit error occurs in a bit position designated by X, as shown in FIG. 12, the band-by-band code 102-3 numbered (4) separated by the prior art variable length code demultiplexer differs from the original one multiplexed by the variable length code multiplexer. Since a Huffman code is used as each of the plurality of band-by-band codes 102-3, the code length of the band-by-band code 102-3 numbered (4) can be erroneously estimated with a considerable probability. As a result, since the forward direction demultiplexing unit 52 cannot separate the band-by-band codes 102-3 numbered (5) through (14), which follows the one numbered (5), from correct locations of the multiplexed code, the following codes separated by the forward direction demultiplexing unit 52 become erroneous ones. These erroneously decoded regions are hatched in FIG. 12.
International publication No. WO92/19074 discloses another prior art variable length code multiplexer and another prior art variable length code demultiplexer, which differ from the ones mentioned above, respectively. The prior art variable length code multiplexer disclosed in that international patent publication counts the length of data generated through variable length coding, and time-division-multiplexes information on the data length into variable length coded data, thereby, even if an error, which is beyond the ability to make an error correction, occurs, preventing the error from exerting an influence upon following blocks (frames in this case). This prior art variable length code multiplexer performs only forward direction multiplexing.
A problem with prior art variable length code multiplexers and prior art variable length code demultiplexers constructed as above is therefore that when a bit error occurs without any application of any error correction code, or when a bit error, which is beyond the ability to make an error correction, occurs even if an error correction code is used, it is impossible to correctly demultiplex codes multiplexed behind a location at which the bit error occurs, and, in the worst case, the range affected by the occurrence of the bit error gets broadened and therefore all codes in the same frame are erroneously separated because multiplexing and demultiplexing are carried out only with respect to the forward direction.